package P1线性结构.LeetCode单调栈与单调队列;


import java.util.ArrayDeque;

public class LC862 {
    public int shortestSubarray(int[] nums, int k) {
        long[] preSum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            preSum[i + 1] = nums[i] + preSum[i];
        }
        int len = nums.length + 1;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < preSum.length; i++) {
            while (!queue.isEmpty() && preSum[i] - preSum[queue.peekFirst()] >= k) {
                len = Math.min(len, i - queue.pollFirst());
            }
            while (!queue.isEmpty() && preSum[i] <= preSum[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        return len < nums.length + 1 ? len : -1;
    }
}